package com.cheng.dataStructure.tree;

/**
 * @User Administrator
 * @Classname ArrBinaryTreeDemo
 * @Project Data-structure-and-algorithm
 * @Description 顺序存储二叉树代码实现：
 * 基本说明：
 * 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。
 * >顺序存储二叉树的特点:
 * 1)顺序二叉树通常只考虑完全二叉树
 * 2)第n个元素的左子节点为2 * n+ 1
 * 3)第n个元素的右子节点为2 * n+ 2
 * 4)第n个元素的父节点为(n-1)/ 2
 * 5) n:表示二叉树中的第几个元素，按O开始编号
 * 要求:
 * 1)要求以数组的方式来存放二叉树的结点，如arr: [1,2,3,4,5,6,7]
 * 2)要求在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成二叉树结点的遍历
 * @Author wpcheng
 * @Create 2021-08-29-9:12
 * @Version 1.0
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};//存放二叉树节点的有序数组

        ArrBinaryTree tree = new ArrBinaryTree(arr);
        tree.preOrder();
        tree.infixOrder();
        tree.postOrder();

    }
}

class ArrBinaryTree{
    public int[] arr;

    public ArrBinaryTree(int[] arr){
        this.arr = arr;
    }

    //重载preOrder
   public void preOrder(){
        preOrder(0);
    }
    public void infixOrder(){
        infixOrder(0);
    }

    public void postOrder(){
        postOrder(0);
    }

    /**
     * 用前序遍历的方式遍历数组得到二叉树节点
     * @param index 当前数组下标
     */
    public void preOrder(int index){
        if (arr.length == 0 || arr == null ){
            System.out.println("数组为空，无法遍历");
        }

        //得到当前节点
        System.out.println(arr[index]);

        //向当前节点的左子节点递归
        if (2 * index + 1 < arr.length){
            preOrder(2 * index + 1);
        }

        //向当前节点的右子节点递归
        if (2 * index + 1 < arr.length){
            preOrder(2 * index + 2);
        }
    }

    /**
     * 用中序遍历的方式遍历数组得到二叉树节点
     * @param index 当前数组下标
     */
    public void infixOrder(int index){
        if (arr.length == 0 || arr == null ){
            System.out.println("数组为空，无法遍历");
        }

        //向当前节点的左子节点递归
        if (2 * index + 1 < arr.length){
            preOrder(2 * index + 1);
        }

        //得到当前节点
        System.out.println(arr[index]);

        //向当前节点的右子节点递归
        if (2 * index + 1 < arr.length){
            preOrder(2 * index + 2);
        }
    }


    /**
     * 用后序遍历的方式遍历数组得到二叉树节点
     * @param index 当前数组下标
     */
    public void postOrder(int index){
        if (arr.length == 0 || arr == null ){
            System.out.println("数组为空，无法遍历");
        }

        //向当前节点的左子节点递归
        if (2 * index + 1 < arr.length){
            preOrder(2 * index + 1);
        }

        //向当前节点的右子节点递归
        if (2 * index + 1 < arr.length){
            preOrder(2 * index + 2);
        }

        //得到当前节点
        System.out.println(arr[index]);


    }


}







